sliding window 這主題的最後一道練習題，明天將討論 Grid Traversal。

30. Substring with Concatenation of All Words(hard)

題目敘述: 給一個字串 s，還有一個都是同長度字串的陣列 words
以下，我將 words 裡的字串都代稱為 word。此題要求我們在 s 找到所有 word 任意順序相接的子字串的起始索引。。

題目中的例子 ， words = ["ab","cd","ef"], 那麼全部排列並相接字串就會是 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd"與 "efcdab"

思路分析

1. Sliding Window 設計 lptr 指向視窗內第一個 word 的起始位置，rptr 指向視窗內最後一個 word 的起始位置

   • lptr 指向的字串以下我稱為「舊字串」（oldW），
   • rptr 指向的字串稱為「新字串」（newW），因為 rptr 指向的字串還沒有加入視窗中。

2. 起始位置考量
   視窗的起始指針 lptr 不一定要從 0 開始。由於每個字串的長度都是固定的，因此可以 lptr 從索引 0 到 word.size()-1 嘗試不同的起始點，lptr 會依字串長度做位移。例如，在 s = "abar" 中，words = ["bar"]，因此我們要返回 [1]

3. Counter 設計 因為 words 中的字串可能重複出現，所以我們需要使用一個計數器 w_ctr 來記錄 words 中各字串的次數，同時在滑動視窗的過程中，再使用一個計數器 w_window_ctr 來統計視窗中各字串的出現次數。一旦兩個計數器的內容完全一致，代表找到符合條件的子字串，便將 lptr 推入我們的答案中!

4. 滑動視窗操作

   • 當右移視窗時，需要更新視窗內的字串計數器 w_window_ctr。
   • 當視窗內某個字串的次數超過 words 中該字串的次數時，代表視窗中包含了不需要的字串，這時就需要將左指針 lptr 右移。

5. 特例處理 如果 lptr 和 rptr 同時卡住不動（即視窗內無法匹配更多字串），那麼就同時移動兩個指針。

class Solution {
public:
   vector<int> f(string s, vector<string>& words, int i, unordered_map<string,int> w_ctr) {
        vector<int> res;
        const int w_size = words[0].size();
        const int w_num = words.size();
        int lptr = i, rptr = i;
        int w_window_num = 0;
        unordered_map<string, int> w_window_ctr;
        while (rptr + w_size-1 < s.size()) {
            string newW = s.substr(rptr, w_size);
            if (w_window_num < w_num && w_ctr.count(newW) && w_ctr[newW] > w_window_ctr[newW]) {
                w_window_ctr[newW]++;
                w_window_num++;
                if(w_window_num == w_num) {
                   res.push_back(lptr);
                   string oldW = s.substr(lptr, w_size);
                   w_window_ctr[oldW]--;
                   w_window_num--;
                   lptr += w_size;
                }
                rptr += w_size;
            }
            else if(lptr < rptr) {
                string oldW = s.substr(lptr, w_size);
                if(w_ctr[oldW] > 0) {
                    w_window_ctr[oldW]--;
                    w_window_num--;
                }
                lptr += w_size;
            } else {
                lptr += w_size;
                rptr += w_size;
            }
        }
        return res;
    }

    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        unordered_map<string, int> w_ctr;
        for (string s: words) {
            w_ctr[s]++;
        }
        for (int i = 0; i < words[0].size(); i++) {
            vector<int> tmp = f(s, words, i, w_ctr); 
			res.insert(res.end(), tmp.begin(), tmp.end());
        }
        return res;
    }
};

時間複雜度: O(字串長度 * word 長度)

另外，詢問了 Chatgpt 我程式碼的改進空間

1. 程式碼的可讀性和簡潔性：
   在 f 函數中，lptr 和 rptr 的處理邏輯稍微有些冗長，代碼可以進一步簡化和提高可讀性。例如，判斷邏輯可以拆成幾個小步驟，使得每一步的目標更加明確。
2. 重複的 substr 操作：
   s.substr(lptr, w_size) 和 s.substr(rptr, w_size) 會頻繁出現，這個操作可能會產生較多的開銷。可以儘量避免在同一個索引上重複調用 substr，將其結果保存在變量中使用。
3. 無法匹配的情況下進行早期退出：
   如果當前的 newW 根本不在 w_ctr 中，意味著這個窗口內肯定不會有匹配結果，可以立刻右移窗口，避免無謂的操作。

最近忙著寫論文QQ，之後有空再回頭將這題寫得更漂亮!